package com.sx.sx1.lintcode.day717;

public class LC3707 {

    static class Solution {
        /**
         * @param bookings: Flight booking information
         * @param n: Total number of flights
         * @return: Number of seats booked per flight
         */
        public int[] corpFlightBookings(int[][] bookings, int n) {
            //差分数组
            int[] d = new int[n+2];
            for (int[] v : bookings) {
                int start = v[0];
                int end = v[1];
                int val = v[2];
                d[start] +=val;
                d[end+1] -=val;
            }

            int s =0;
            int[] ans = new int[n];
            for (int i = 1; i <=n ; i++) {
                s+=d[i];
                ans[i-1]=s;
            }
            return ans;
        }
    }


    public static void main(String[] args) {
        Solution obj= new Solution();
        int[][] arr1 = {{1,2,10},{2,4,20},{2,5,25}};
        int[] data1 = obj.corpFlightBookings(arr1,5);
        for (int i : data1) {
            System.out.print(i+" ");
        }

        System.out.println();
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有189条未读消息，请及时查看
3707 · 统计航班预订信息
算法
中等
通过率
54%

题目
题解4
笔记
讨论
排名
记录
描述
现在有 n 个航班，航班编号从 1 到 n。

现在给定一个航班预订信息表 bookings，对于表中的预订记录 bookings[i] = [start, end, seats] 表示从 start 到 end（均包含这两个编号）的 每一个航班都预订了 seats 个座位。

返回长度为 n 的预订结果表 result，分别记录从第 1 到第 n 个航班编号所预订的座位总数。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1
≤
𝑛
≤
1
0
5
1≤n≤10
5

1
≤
𝑏
𝑜
𝑜
𝑘
𝑖
𝑛
𝑔
𝑠
.
𝑙
𝑒
𝑛
𝑔
𝑡
ℎ
≤
1
0
5
1≤bookings.length≤10
5

𝑏
𝑜
𝑜
𝑘
𝑖
𝑛
𝑔
𝑠
[
𝑖
]
.
𝑙
𝑒
𝑛
𝑔
𝑡
ℎ
=
=
3
bookings[i].length==3
1
≤
𝑠
𝑡
𝑎
𝑟
𝑡
≤
𝑒
𝑛
𝑑
≤
𝑛
1≤start≤end≤n
1
≤
𝑠
𝑒
𝑎
𝑡
𝑠
≤
1
0
4
1≤seats≤10
4


样例
样例 1：

输入：
bookings = [[1,2,10],[2,4,20],[2,5,25]]
n = 5
输出：
[10,55,45,45,25]
解释：
航班编号:       1    2    3    4    5
记录 1 :       10   10
记录 2 :            20   20   20
记录 3 :            25   25   25   25
总座位 :       10   55   45   45   25
样例 2：

输入：
bookings = [[1,2,10],[2,2,20]]
n = 2
输出：
[10,30]
解释：
航班编号:       1    2
记录 1 :       10   10
记录 2 :            20
总座位 :       10   30
标签
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */